from block import Block
# 树节点
class TreeNode:
    # 数字块
    _block = None;
    # 上下左右的子树，其数据结构为 块哈希 映射下一个Treenode
    children = [{},{},{},{}];

    def __init__(self, block):
        self._block = block;

    # 是否为解
    def isSolution(self):
        for i in range(4):
            if len(self.children[i]) > 0:
                return True
        return False

    def up(self):
        block = Block(self._block._value)
        block.up()
        return block;

    def down(self):
        block = Block(self._block._value)
        block.down()
        return block;

    def left(self):
        block = Block(self._block._value)
        block.left()
        return block;

    def right(self):
        block = Block(self._block._value)
        block.right()
        return block;

    def fill(self):
        return self._block.randomFill()


    def isWin(self):
        return self._block.isWin()
# 死亡集合
deadSet = None;
# 块哈希到树节点映射
block2TreeNode = None;
# 进行搜索
def search(treeNode, winValue, dirStr):
    treeNode._block.print()
    global block2TreeNode, deadSet
    # 如果已经为结果，直接返回，剪枝
    if treeNode.isWin(winValue):
        print('找到解%s' % dirStr)
        print('解为')
        treeNode._block.print()
        # 找到解，剪枝
        return True;
    # 搜索4个方向
    for i in range(4):
        if i == 0:
            tempStr = dirStr + 'u->'
            newBlock = treeNode.up()
            

        elif i == 3:
            tempStr = dirStr + 'd->'
            newBlock = treeNode.down()

        elif i == 2:
            tempStr = dirStr + 'l->'
            newBlock = treeNode.left()

        else:
            tempStr = dirStr + 'r->'
            newBlock = treeNode.right()

        # 如果操作无意义
        if newBlock == treeNode._block:
            print('之前：')
            treeNode._block.print()
            print('之后: ')
            newBlock.print()
            # 跳过
            print('无意义操作%s' % dirStr)
            continue
        # 如果赢了
        if newBlock.isWin(winValue):
            continue;

        # 填充其他块
        subs = newBlock.randomFill()

        # 如果已经死了，直接继续
        if newBlock.isDead(winValue):
            continue;

        # 遍历填充后的块
        for sub in subs:
            # 该块是否有对应答案
            treeNode = block2TreeNode.get(sub)
            # 如果还没有答案
            if treeNode == None:
                # 新建一个节点
                treeNode = TreeNode(sub)
            # 否则的话，看下一个块
            else:
                continue;
            # 如果这个方向可以找到解
            if search(treeNode, winValue, tempStr):
                # 全局存储
                block2TreeNode[sub] = treeNode;
                # 加枝
                treeNode.children[i][sub] = treeNode; 
            else:
                # 加入死亡节点
                deadSet.add(treeNode._block)
    # 返回是否为解
    return treeNode.isSolution()
# 构造搜索树
def constructTree(block, winValue):
    global block2TreeNode, deadSet
    # 初始化根节点
    root = TreeNode(block)
    # 初始化死亡集合
    deadSet = set();
    # 初始化映射字典
    block2TreeNode = {};
    search(root, winValue, '');
    return root;


if __name__ == '__main__':
    block = Block([
        [0,0,0,0],
        [0,0,0,0],
        [0,0,0,0],
        [0,0,1,1]])
    
    root = constructTree(block, 2)

    # root = TreeNode(block)
    # block.print()
    # print(root.up() == block)
    # root.up().print()
    # print(root.down() == block)
    # root.down().print()
    # print(root.left() == block)
    # root.left().print()
    # print(root.right() == block)
    # root.right().print()